/**********************************
 * Assignment 5: Alien vs Predator
 * Date: 12/04/2011
 *
 * Alexander Miller: ahm82, 2605797
 * David Felty: djf242, 2828357
 * David Hau: dch229, 2586217
 * Hanna Atmer: ha237, 2666426
 **********************************/

package avp.alien;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

import avp.Agent;
import avp.Edge;
import avp.EdgeState;
import avp.Info;
import avp.Move;
import avp.Node;
import avp.Ship;

public class Alien implements Agent {
	
	enum AlienState {
		EXPLORING, INVESTIGATING, CHASING, BURNING_TO_KILL, SEARCHING_LAST_LOCATION, HAS_SCANNER
	}
	
	// The alien's current view of the ship
	private Ship ship;
	private AlienState state;
	private Edge lastKnownLocation;
	private Random rand = new Random();
	private Set<Edge> usedEdges = new HashSet<Edge>();
	private Stack<Edge> investPath = new Stack<Edge>();
	private HashMap<Edge,Integer> weights = new HashMap<Edge,Integer>();
	private boolean hasScanner = false;
	
	final int BURN_TIME = 5;
	final int ALIEN_SENSE = 16;
	
	public Alien() {
		state = AlienState.EXPLORING;
	}

	@Override
	public void init(Ship ship) {
		if (ship != null) {
			this.ship = ship;
			updateWeights();
		}
	}

	@Override
	public Move nextMove(Info info) {
		// update the ship map
		if (info.atScanner) init(info.ship);
		if (info.atScanner) hasScanner = true;
		
		if (!investPath.isEmpty()) lastKnownLocation = investPath.pop();
				
		//figure out what attitude the AI should have
		if (hasScanner) state = AlienState.HAS_SCANNER; 
		else if (info.adversaryPresent) state = AlienState.CHASING;
		else if (info.adversaryThruWall != null) state = AlienState.BURNING_TO_KILL;
		else if (lastKnownLocation != null) state = AlienState.SEARCHING_LAST_LOCATION;
		else if (closedDoorAdjacent(info) != null) state = AlienState.INVESTIGATING;
		else state = AlienState.EXPLORING;
	

		Move m = new Move();
		
		if (state == AlienState.HAS_SCANNER) {
			m.edge =  dijkstra(ship.getAlienLocation(), ship.getPredatorLocation()).get(0);
			if (m.edge.getState() == EdgeState.CLOSED || m.edge.getState() == null) {
				m.move = false;
				m.changeState = true;
			}
			else {
				m.move = true;
				m.changeState = false;
			}
			return m;
		}
		if (state == AlienState.EXPLORING) { // searching the ship for the predator
			return randomMove(info);
		}
		else if (state == AlienState.INVESTIGATING) { // investigating paths formed by closed doors
			m.edge = closedDoorAdjacent(info);
			lastKnownLocation = m.edge;
			m.move = false;
			m.changeState = true;
			return m;
		}
		else if (state == AlienState.CHASING) { // chasing the currently sensed predator
			lastKnownLocation = null;
			m.edge = info.adversaryDirection;
			
			if (m.edge.getState() == EdgeState.CLOSED || m.edge.getState() == null) {
				m.move = false;
				m.changeState = true;
			}
			else {
				addUsed(info, m);
				m.move = true;
				m.changeState = false;
			}
			return m;
		}
		else if (state == AlienState.BURNING_TO_KILL) {
			m.edge = info.adversaryThruWall;
			lastKnownLocation = m.edge;
			m.move = false;
			m.changeState = true;
			return m;
		}
		else if (state == AlienState.SEARCHING_LAST_LOCATION) {
			m.edge = lastKnownLocation;
			lastKnownLocation = null;
			addUsed(info, m);
			m.move = true;
			m.changeState = false;
			return m;
		}
		else return null; // should never be reached, if null is returned then there is an error
	}
	
	/**
	 * sets the weights of the alien's personal ship based on their state and the BURN_TIME constant
	 */
	private void updateWeights() {
		weights.clear();
		
		for (Edge e : ship.getEdges()) {
			if (e.getState() == EdgeState.CLOSED || e.getState() == null) weights.put(e, 1 + BURN_TIME);
			else if (e.getState() == EdgeState.OPEN || e.getState() == EdgeState.BURNED) weights.put(e, 1);
		}
	}
	
	/**
	 * @return the first closed door the alien finds next to it if one exists
	 * @return null if none exist
	 */
	private Edge closedDoorAdjacent(Info info) {
		for (Edge e : info.adjacentEdges) {
			if (e.getState() == EdgeState.CLOSED) return e;
		}
		return null;
	}

	private Move randomMove(Info info) {
		Move m = new Move();
		Set<Edge> edges = new HashSet<Edge>();
		
		for (Edge e : info.adjacentEdges) {
			if (!usedEdges.contains(e)) edges.add(e);
		}

		if (edges.size() > 0) {
			m.edge = (Edge) edges.toArray()[rand.nextInt(edges.size())];
			usedEdges.add(m.edge);
			m.move = true;
			m.changeState = false;
			return m;
		}
		
		for (Edge e : info.allEdges) {
			if (e.getState() == EdgeState.BURNED && !usedEdges.contains(e)) edges.add(e);
		}
		if (edges.size() > 0) {
			m.edge = (Edge) edges.toArray()[rand.nextInt(edges.size())];
			usedEdges.add(m.edge);
			m.move = true;
			m.changeState = false;
			return m;
		}
		
		for (Edge e : info.allEdges) {
			if (!info.adjacentEdges.contains(e)) edges.add(e);
		}
		m.edge = (edges.size() > 0) ? (Edge) edges.toArray()[rand.nextInt(edges.size())] : (Edge) info.adjacentEdges.toArray()[rand.nextInt(info.adjacentEdges.size())];
		if (m.edge.getState() == EdgeState.BURNED)
		{
			m.move = true;
			m.changeState = false;
		}
		else {
			m.move = false;
			m.changeState = true;
		}
		return m;
	}
	
	private void addUsed(Info info, Move move) {
		for (Edge e : info.allEdges) {
			usedEdges.add(e);
		}
	}
	
	public AlienState getState() {
		return state;
	}
	
	public String ident() {
		return "Makya";
	}
	
	private List<Edge> dijkstra(Node start, Node end) {
		return dijkstraBase(start, end, new HashMap<Node,Integer>());
	}
	
	// Finds the lowest cost path between start and end; returns null if no path exists
	private List<Edge> dijkstraBase(Node start, Node end, final Map<Node,Integer> dist) {
		start = getEqualNode(start);
		final Set<Node> marked = new HashSet<Node>();
		final Map<Node,Node> prev = new HashMap<Node,Node>();
		final Queue<Node> q = new PriorityQueue<Node>(16, new Comparator<Node>() {
			public int compare(Node n1, Node n2) {
				return dist.get(n1) - dist.get(n2);
			}
		});
		dist.put(start, 0);
		q.add(start);
		
		while (!q.isEmpty()) {
			Node u = q.poll();
			if (u.equals(end)) break;
			marked.add(u);
			Integer du = dist.get(u); 					// du = distance to u
			if (du == null) break; 						// We reached a node that is infinity
			
			for (Node v : getAdjacentNodes(u)) {
				if (marked.contains(v)) continue;
				Integer dv = dist.get(v); 				// dv = distance to v
				int alt = du + weights.get(edgeTo(u, v));		// alt = alternate dist to v
				if (dv == null || alt < dv) {			// null dv represents infinity
					dist.put(v, alt);					// Update new shortest path to v
					prev.put(v, u);
					q.remove(v);						// Reorder v in q
					q.add(v);
				}
			}
		}
		
		return backtrack(start, end, prev);
	}
	
	// Backtracks through prev from end to start, returning the path of edges in between
	private List<Edge> backtrack(Node start, Node end, Map<Node,Node> prev) {
		if (!prev.containsKey(end)) return null;
		
		List<Edge> es = new ArrayList<Edge>();
		Node a = end;
		Node b = prev.get(a);
		while (b != null) {
			es.add(edgeTo(a, b));
			a = b;
			b = prev.get(a);
		}
		Collections.reverse(es); // Reverse the backtrack
		return es;
	}
	
	private Node getEqualNode(Node x) {
		for (Node n : ship.getNodes()) {
			if (x.equals(n)) {
				if (x != n) System.out.println("Warning: start node should come from ship it is called with");
				return x;
			}
		}
		throw new IllegalArgumentException("Supplied start node doesn't exist in graph");
	}
	
	private Set<Node> getAdjacentNodes(Node n) {
		Set<Node> adjacentNodes = new HashSet<Node>();
		for (Edge e : n.getAdjacent()) {
			adjacentNodes.add(e.other(n));
		}
		return adjacentNodes;
	}
	
	private Edge edgeTo(Node a, Node b) {
		for (Edge e1 : a.getAdjacent()) {
			for (Edge e2 : b.getAdjacent()) {
				if (e1 == e2) return e1;
			}
		}
		throw new IllegalArgumentException(a + " not adjacent to " + b);
	}
}
